1. Field of the Invention
This invention relates to data processing systems, and in particular to adaptive replacement cache policies that minimize cache misses, and more particularly relates to adaptive replacement based cache policies that resize cache memory.
2. Description of the Related Art
Computer memory systems generally comprise two memory levels: main (or cache) and auxiliary. Cache memory is faster than auxiliary memory, but is also significantly more expensive. Consequently, the size of the cache memory is usually only a fraction of the size of the auxiliary memory.
Caching is one of the fundamental metaphors in modem computing. It is widely used in storage systems, databases, web servers, middleware, processors, file systems, disk drives, and operating systems. Memory caching is also used in varied and numerous other applications such as data compression and list updating. As a result a substantial progress in caching algorithms could affect a significant portion of the modern computation stack.
Both cache and auxiliary memories are managed in units of uniformly sized items known as pages of memory or cache lines. Requests for pages of memory (hereinafter “pages”) are first directed to the cache. A request for a page is directed to the auxiliary memory only if the page is not found in the cache. In this case, a copy is “paged in” to the cache from the auxiliary memory. This is called “demand paging” and it precludes “pre-fetching” pages from the auxiliary memory to the cache. If the cache is full, one of the existing pages must be paged out before a new page can be brought in.
A replacement policy determines which page is “paged out.” A commonly used criterion for evaluating a replacement policy is the hit ratio, the frequency at which a page is found in the cache as opposed to finding the page in auxiliary memory. The miss rate is the fraction of pages paged into the cache from the auxiliary memory. The replacement policy goal is to maximize the hit ratio measured over a very long trace while minimizing the memory overhead involved in implementing the policy.
Most current replacement policies remove pages from the cache based on “recency” that is removing pages that have least recently been requested, “frequency” that is removing pages that are not often requested, or a combination of recency and frequency. Certain replacement policies also have parameters that must be carefully chosen or “tuned” to achieve optimum performance.
The most commonly used replacement policy is based on the concept of replace the least recently used (LRU) page. The LRU policy focuses solely on recency, always replacing the least recently used page. LRU, as one of the original replacement policies, has many areas which may be improved upon.
LRU has several advantages: it is relatively simple to implement and responds well to changes in the underlying stack depth distribution model. However, while the stack depth distribution model captures recency, it does not capture frequency. Each page is equally likely to be referenced and stored in cache. Consequently, the LRU model is useful for treating the clustering effect of locality but not for treating non-uniform page referencing. Additionally, the LRU model is vulnerable to one-time-only sequential read requests, or scans, that replace higher-frequency pages with pages that would not be requested again, reducing the hit ratio. In other terms, the LRU model is not “scan resistant.”
Another commonly used replacement policy is the least frequently used (LFU) algorithm. As suggested by the name, the LFU policy focuses on frequency, always replacing the least frequently used page. While the LFU policy is scan-resistant, it presents several drawbacks. The LFU policy requires logarithmic implementation complexity in cache size and pays almost no attention to recent history. In addition, the LFU policy does not adapt well to changing access patterns since it accumulates state pages with high frequency counts that may no longer be useful.
Over the past few years, interest has focused on combining recency and frequency in various ways, attempting to bridge the gap between LRU and LFU. Three replacement policy algorithms exemplary of this approach are Adaptive Replacement Cache (ARC), CLOCK with Adaptive Replacement (CAR), and CAR with Temporal filtering (CART).
The basic idea behind ARC is to maintain two LRU lists of pages. One list, L1, contains pages that have been seen only once “recently,” while the second list, L2, contains pages that have been seen at least twice “recently.” The items that have been seen twice within a short time have a low inter-arrival rate, and therefore are thought of as “high-frequency.” In other words, L1 captures “recency” while L2 captures “frequency.” The ARC policy dynamically decides, in response to an observed workload, whether to replace an item from L1 or L2.
CAR builds on ARC by implementing portions of the CLOCK algorithm. The CLOCK algorithm maintains a page reference bit with every page. When a page is first brought into the cache, its page reference bit is set to zero. The pages in the cache are organized in a circular buffer known as a clock. On a hit to a page, the page reference bit is set to one. Replacement is done by moving a clock hand through the circular buffer and replacing pages with page reference bits set to zero.
The basic idea of CAR is to maintain two clocks, for example T1 and T2 where T1, contains pages with recency or short-term utility and T2 contains pages with frequency or long-term utility. New pages are first inserted into T1 and graduate to T2 upon passing a certain test of long-term utility.
The algorithms ARC and CAR consider two consecutive hits to a page as a test of long-term utility. At upper levels of memory hierarchy, for example, virtual memory, databases, and file systems, consecutive page hits occur fairly quickly. Such consecutive page hits are not a guarantee of long-term utility. This problem is solved by the temporal filtering of CART. The basic idea behind CART is to maintain a temporal locality window such that pages that are re-requested within the window are of short-term utility whereas pages that are re-requested outside the window are of long-term utility.
ARC, CAR, and CART greatly maximize the hit rate while minimizing the computational and space overhead involved with implementing cache replacement policies. However, each policy suffers from not being able to grow or shrink the cache. When shrinking an LRU cache, the algorithm simply discards the least-recently used pages, and when growing the LRU cache, the algorithm adds storage as empty pages. Since ARC, CAR, and CART maintain multiple lists, shrinking or growing the cache is not as simple as adding to or removing from the LRU.
Shrinking the cache is desirable in situations where resources need to be reallocated. For example, common computing systems have the capability to run multiple operating systems. Software that enables the computing system to run multiple operating systems “virtualizes” the operating system. The virtual operating system has access to the computing system's resources such as processor, cache (also referred to as RAM), and auxiliary memory. The virtual operating system operates in what is commonly referred to as “sandbox environment,” insulated from other virtual operating systems.
As a new virtual operating system is started, cache needs to be allocated to the new virtual operating system and consequently removed from other programs. Removing, or shrinking the size of the cache allocated to a particular virtual operating system is a simple task for LRU algorithms, as discussed above. However, there is no method for shrinking or growing cache with ARC, CAR, and CART algorithms.
From the foregoing discussion, it should be apparent that a need exists for an apparatus, system, and method that adjust cache size using ARC, CAR, and CART algorithms. Beneficially, such an apparatus, system, and method would monitor application load changes and update cache size by adding new empty pages for cache growth, and to choose pages to discard for cache shrinkage.